ABC 371E

利用好 $a_i\le n$ 的条件，转化题意。

一种转化方式如下：定义 $P(x)$ 为包含 $x$ 的连续子序列数量，则题目所求即为 $\sum _{i=1}^{n}P(i)$。

我们按照提示二转化题意。注意到 $a_i\le n$ 的特殊条件，$f(l,r)$ 可以自然转换为在形如 “$i\in [1,n]$ 出现在 $a_l,a_{l+1},\cdots ,a_r$" 的 $n$ 个条件中满足的数量，因此该转化是正确的。

接下来的任务就是如何快速计数 $P(x)$，考虑正难则反，计算不包含 $x$ 的子序列数量。考虑将数列中 $x$ 的出现作为分割符分割序列，对于每个不含 $x$ 的长 $l_i$ 的子序列，其对答案的贡献为 ${\displaystyle \frac{l_i(l_i+1)}{2}}$，求和后用其减去 ${\displaystyle \frac{n(n+1)}{2}}$ 即为答案。依据均摊分析，可以证明对于所有的 $i$ 该过程可以在 $\mathcal{O}(n)$ 的时间复杂度内完成所有计算。